package middle;

import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;

public class Solution_143 {

    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        // 分割
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 反转second
        ListNode first = head, second = slow.next, secondPre = null;
        slow.next = null;
        while (second != null) {
            ListNode temp = second.next;
            second.next = secondPre;
            secondPre = second;
            second = temp;
        }
        second = secondPre;

        // 合并
        while (second != null) {
            ListNode temp = first.next;
            first.next = second;
            second = second.next;
            first = first.next;
            first.next = temp;
            first = first.next;
        }
    }

    public static void main(String[] args) {
        Solution_143 model = new Solution_143();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        //        head.next.next = new ListNode(3);
        //        head.next.next.next = new ListNode(4);
        //        head.next.next.next.next = new ListNode(5);
        model.reorderList(head);
        System.out.println();
    }

    static class ListNode {

        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    private static List<Cost> merge(List<Cost> hList, List<Cost> uList) {
        Date max = null, min = null;
        for (Cost cost : hList) {
            max = max == null ? cost.eDate : cost.eDate.after(max) ? cost.eDate : max;
            min = min == null ? cost.sDate : cost.sDate.before(min) ? cost.sDate : min;
        }
        for (Cost cost : uList) {
            max = max == null ? cost.eDate : cost.eDate.after(max) ? cost.eDate : max;
            min = min == null ? cost.sDate : cost.sDate.before(min) ? cost.sDate : min;
        }
        return null;
    }

    static class Cost {
        public Cost() {}

        public Date sDate;
        public Date eDate;
        public int cost;
    }

    private static void demo01() throws Exception {
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
        List<Cost> hList = new ArrayList<>();
        Cost h1 = new Cost();
        h1.sDate = sdf.parse("2022-05-01");
        h1.eDate = sdf.parse("2022-05-10");
        h1.cost = 1;
        hList.add(h1);

        List<Cost> uList = new ArrayList<>();
        Cost u1 = new Cost();
        u1.sDate = sdf.parse("2022-05-11");
        u1.eDate = sdf.parse("2022-05-20");
        u1.cost = 1;
        uList.add(u1);

        //System.out.print(sdf.format(h1.sDate) + ", " + sdf.format(h1.eDate) + ", " + h1.cost);

        List<Cost> nList = merge(hList, uList);
        if(nList != null) {
            for(Cost c : nList) {
                System.out.print(sdf.format(c.sDate) + ", " + sdf.format(c.eDate) + ", " + c.cost);
            }
        }
    }

}
